package newcoder_exp.justPractise;

import java.util.*;
import org.junit.*;

public class NC20 {
    public ArrayList<String> restoreIpAddresses(String s) {
        dfs(new StringBuilder(s), 0, 0);
        return res;
    }

    ArrayList<String> res = new ArrayList<>();

    public void dfs(StringBuilder sb, int idx, int time) {
        if (time == 3) {
            String[] strs = sb.toString().split("\\.");
            if (strs.length < 4)
                return;
            for (int i = 0; i < 4; i++) {
                int t = Integer.parseInt(strs[i]);
                if (strs[i].charAt(0) == '0' && strs[i].length() > 1 || t < 0 || t > 255) {
                    return;
                }
            }
            res.add(sb.toString());
            return;
        }
        if (idx + 2 <= sb.length()) {
            sb.insert(idx + 1, '.');
            dfs(sb, idx + 2, time + 1);
            sb.deleteCharAt(idx + 1);
        }
        if (idx + 2 <= sb.length()) {
            sb.insert(idx + 2, '.');
            dfs(sb, idx + 3, time + 1);
            sb.deleteCharAt(idx + 2);
        }
        if (idx + 3 <= sb.length() && sb.charAt(idx) > '0' && sb.charAt(idx) <= '2') {
            sb.insert(idx + 3, '.');
            dfs(sb, idx + 4, time + 1);
            sb.deleteCharAt(idx + 3);
        }
    }

    @Test
    public void test() {
        ArrayList<String> res = restoreIpAddresses("010010");
        System.out.println(res);
    }
}
